<?php
/**
 * 反转单链表
 */

class Node
{
    public $data;//节点数据
    public $next;//后继节点
    
    public function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
}

class ReverseLinkedList
{
    public $header;//头节点
    
    public function __construct($data)
    {
        $this->header = new Node($data);
    }
    
    /**
     * 查找节点
     *
     * @param string $item 节点数据
     *
     * @return object
     */
    public function find($item)
    {
        $current = $this->header;
        while($current->data != $item)
        {
            $current = $current->next;
        }
        
        return $current;
    }
    
    /**
     * 插入节点
     *
     * @param string $item 插入节点
     * @param string $new  插入的新节点
     *
     * @return boolean
     */
    public function insert($item,$new)
    {
        $current = $this->find($item);
        $new = new Node($new);
        $new->next = $current->next;
        $current->next = $new;
        return true;
        
    }
    
    /**
     * 显示
     */
    public function show()
    {
        $current = $this->header;
        while($current->next == NULL)
        {
            echo '空的';
            return;
        }
        
        
        
        while($current->next != NULL)
        {
            echo $current->next->data.'  ';
            $current = $current->next;
        }
    }
    
    /**
     * 反转显示
     */
    public function reverse()
    {
        $pre = null;
        $current = $this->header;
        while($current != NULL)
        {
            $tmp = $current->next;//将当前节点的下一个节点 用一个变量存储 A B C
            $current->next = $pre;
            $pre = $current; //header A B
            $current = $tmp;//A B
        }
        return $pre;
    }
}

$reverse_linked_list = new ReverseLinkedList("header");
$reverse_linked_list->insert("header",'A');
$reverse_linked_list->insert("A",'B');
$reverse_linked_list->insert("B",'C');
$reverse_linked_list->insert("C",'D');
$reverse_linked_list->insert("D",'E');
$reverse_linked_list->show();

$reverse_linked_list->reverse();